package C006;

import java.util.Arrays;

/**
 * ClassName: BinarySearch
 * Package: C005
 * Description:
 *
 * @Author BCXJ
 * @Create 2024/11/27 21:44
 * @Version 1.0
 * @Since 1.0
 */
public class BinarySearch {

    public static void main(String[] args) {
        int n = 10000;
        int length = 8;
        int size = 100;

        for (int i = 0; i < n; i++) {
            int[] arr = generateRandomArray(length, size);
            Arrays.sort(arr);
            int[] arr2 = Arrays.copyOf(arr, arr.length);
            int target = (int) (Math.random() * size);
            int index1 = binarySearch(arr, target);
            int index2 = violenceOperation(arr2, target);
            if(index1 != index2 && arr[index2] != arr2[index1]) {
                System.out.println("error!!!!");
                System.out.println(Arrays.toString(arr2));
                System.out.println(target);
                System.out.println(index1);
                System.out.println(index2);
                return;
            }
        }

        System.out.println("success !!!");

    }

    /**
     * 暴力找出对应的下标
     * @param nums
     * @param target
     * @return
     */
    public static int violenceOperation(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == target) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 二分查找
     * @param nums
     * @param target
     * @return 返回元素的下标
     */
    public static int binarySearch(int[] nums, int target) {
        if(nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int midIndex = 0;
        while(left <= right) {
            midIndex = left + ((right - left) >> 2);
            if(target == nums[midIndex]) {
                return midIndex;
            }else if(target < nums[midIndex]) {
                right = midIndex - 1;
            } else if (target > nums[midIndex]) {
                left = midIndex + 1;
            }
        }
        return -1;
    }



    public static int[] generateRandomArray(int n, int k) {
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random() * k) + 1; // 1 - k
        }
        return arr;
    }
}
